package gsw.tool.arithmetic.astar;

import java.util.ArrayList;
import java.util.List;

import gsw.tool.common.ToolShow;

/**
 * A-Star（A*)算法是一种静态路网中求解最短路最有效的方法。它使用估价函数表示走下一个点时的路程，然后从能走的点中选取路程最小的那个点开始走，直到走到终点。估价函数公式表示为：f(n)=g(n)+h(n)，其中f(n)是节点n从初始点到目标点的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。
 * A-Star算法分为简化版和完整版。
 * A-Star算法的应用：游戏找路。
 */
public class AStarSimple {
    /**
     * 测试A*算法
     */
    public static void test() {
        Point start = new Point(1, 1);
        Point end = new Point(6, 16);
        int[][] arr = new int[8][18];
        arr[0] = new int[]{3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3};
        arr[1] = new int[]{3, 0, 0, 0, 0, 0, 0, 0, 3, 3, 0, 0, 0, 3, 3, 0, 3, 3};
        arr[2] = new int[]{3, 3, 3, 0, 3, 3, 3, 0, 3, 3, 0, 3, 0, 0, 0, 0, 3, 3};
        arr[3] = new int[]{3, 3, 3, 0, 3, 3, 3, 0, 0, 0, 0, 3, 0, 3, 3, 3, 3, 3};
        arr[4] = new int[]{3, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 3, 0, 0, 0, 3, 3, 3};
        arr[5] = new int[]{3, 0, 3, 3, 3, 0, 0, 0, 0, 0, 3, 0, 3, 3, 0, 0, 0, 3};
        arr[6] = new int[]{3, 0, 0, 3, 3, 3, 3, 3, 3, 0, 0, 0, 3, 3, 3, 3, 0, 3};
        arr[7] = new int[]{3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3};
        //将起点设为1，表示走过
        arr[start.x][start.y] = 1;
        //将终点设为2
        arr[end.x][end.y] = 2;
        AStarSort(arr, start, end);
        ToolShow.printArr(arr);
    }

    /**
     * A-Star算法简化版只需把走过的点标记为1，当到达终点时，所有为1的点，即为最短路径。适用于没有凹形障碍物的情形，效率比完整版高。
     * 操作步骤：
     * 1. 从起点开始，通过估价函数f(n)，判断周围8个点中，使得路径最短的那个点A，将这个点标记为1(代表走过)；
     * 2. 把A当作新的起点，重复步骤1，直到到达终点。
     *
     * @param map  用一个二维数组表示地图。其中0表示走得通，1表示走过，2表示终点，3表示不能走。
     * @param star 起点
     * @param end  终点
     */
    public static void AStarSort(int[][] map, Point star, Point end) {
        if (star == null && end == null) {
            return;
        }
        if (star.x >= map.length - 1 || star.y >= map[0].length - 1) {
            return;
        }
        //到达终点
        if (star.x == end.x && star.y == end.y) {
            return;
        }
        // 标记当前位置已走过
        map[star.x][star.y] = 1;
        //查找下一个能走的点
        Point next = lookup(map, star, end);
        //以next为起点，重新找寻
        AStarSort(map, next, end);
    }

    /**
     * 查找下一个要走的点
     *
     * @param map   地图
     * @param point 当前点
     * @param end   终点
     * @return 下一个要走的点
     */
    public static Point lookup(int[][] map, Point point, Point end) {
        //保存所有可走的点
        List<Point> result = new ArrayList<>();
        // 表示1维数组下标
        int x = point.x;
        // 表示2维数组下标
        int y = point.y;
        // 如果左边可以走，就添加到result
        if (map[x - 1][y] != 1 && map[x - 1][y] != 3) {
            result.add(new Point(x - 1, y));
        }
        // 如果上边可以走，就添加到result
        if (map[x][y - 1] != 1 && map[x][y - 1] != 3) {
            result.add(new Point(x, y - 1));
        }
        // 如果右边可以走，就添加到result
        if (map[x + 1][y] != 1 && map[x + 1][y] != 3) {
            result.add(new Point(x + 1, y));
        }
        // 如果下边可以走，就添加到result
        if (map[x][y + 1] != 1 && map[x][y + 1] != 3) {
            result.add(new Point(x, y + 1));
        }
        // 如果左上可以走，就添加到result
        if (map[x - 1][y - 1] != 1 && map[x - 1][y - 1] != 3) {
            result.add(new Point(x - 1, y - 1));
        }
        // 如果右下可以走，就添加到result
        if (map[x + 1][y - 1] != 1 && map[x + 1][y - 1] != 3) {
            result.add(new Point(x + 1, y - 1));
        }
        // 如果左下可以走，就添加到result
        if (map[x - 1][y + 1] != 1 && map[x - 1][y + 1] != 3) {
            result.add(new Point(x - 1, y + 1));
        }
        // 如果右下可以走，就添加到result
        if (map[x + 1][y + 1] != 1 && map[x + 1][y + 1] != 3) {
            result.add(new Point(x + 1, y + 1));
        }

        //如果没有可走的点，就退出寻路
        if (result.size() == 0) {
            return null;
        }

        int index = 0;
        int dstance = Integer.MAX_VALUE;
        for (int i = 0; i < result.size(); i++) {
            //使用估价函数，估算两点的距离
            int l = getDistance(point, result.get(i), end);
            //找到距离最小的那个点
            if (dstance > l) {
                index = i;
                dstance = l;
            }
        }

        return result.get(index);
    }

    /**
     * 估价函数：起点与节点的距离+节点与终点的距离
     *
     * @param start 起点
     * @param node  节点
     * @param end   终点
     * @return 估价的距离
     */
    public static int getDistance(Point start, Point node, Point end) {
        return getDistance(start, node) + getDistance(node, end);
    }

    /**
     * 计算两点距离
     *
     * @param start 起点
     * @param end   终点
     * @return 两点距离
     */
    public static int getDistance(Point start, Point end) {
        if (start == null || end == null) {
            return Integer.MAX_VALUE;
        }
        int a = end.x - start.x;
        int b = end.y - start.y;
        int c = (int) Math.sqrt(a * a + b * b);
        return c;
    }

    /**
     * 点
     *
     * @author Asus
     */
    public static class Point {
        int x;// 水平坐标
        int y;// 垂直坐标

        public Point() {
            super();
        }

        public Point(int x, int y) {
            super();
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "Point [x=" + x + ", y=" + y + "]";
        }

    }
}
